package com.goudan.practice.array;

/**
 * 查找0
 * 从大体有序的数组中，找到最靠近正整数和负整数的第一个0，示例 [-2,-4,-6,-8,0,0,0,0,0,5,2,7,1,8]
 * 二分查找变形题
 */
public class FindZero {
    public static void main(String[] args) {
        int[] req = {-2, -4, -6, -8, 0, 0, 0, 0, 0, 5, 2, 7, 1, 8, 10, 11, 16};
        System.out.println(findLeftZero(req));
        System.out.println(findRightZero(req));
    }

    private static int findRightZero(int[] req) {
        int left = 0;
        int right = req.length;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) >> 1;
            if (req[mid] == 0 && req[mid + 1] > 0) {
                return mid;
            }
            if ((req[mid] == 0 && req[mid + 1] == 0) || req[mid] < 0) {
                left = mid;
            }
            if (req[mid] > 0) {
                right = mid;
            }

        }
        return mid;
    }

    private static int findLeftZero(int[] req) {
        int left = 0;
        int right = req.length - 1;
        int mid = 0;
        while (left < right) {
            mid = left + ((right - left) >> 1); // 中点
            if (req[mid] == 0 && req[mid - 1] == 0) {
                right = mid;
            }
            if (req[mid] < 0) {
                left = mid;
            }
            if (req[mid] > 0) {
                left = mid;
            }
            if (req[mid] == 0 && req[mid - 1] < 0) {
                return mid;
            }
        }
        return mid;
    }

}
